package com.example.leetdemo.finash;


import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

public class Solution2279 {

    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        List<Integer> list = new ArrayList<>();
        int max = 0;
        int count = 0;
        for (int i = 0; i < capacity.length; i++) {
            if (capacity[i] > rocks[i]) {
                list.add(capacity[i] - rocks[i]);
                count += capacity[i] - rocks[i];
            } else {

                max++;
            }
        }
        if (count <= additionalRocks) {
            return capacity.length;
        }
        list = list.stream().sorted(Comparator.comparingInt(Integer::intValue)).collect(Collectors.toList());
        for (int i = 0; i < list.size(); i++) {
            if (additionalRocks - list.get(i) >= 0) {
                max++;
                additionalRocks -= list.get(i);
            } else {
                break;
            }
        }
//        if (list.size() > 0) {
//            List<List<Integer>> dpList= new ArrayList<>();
//            for (int i = 0; i < list.size() + 1; i++) {
//                List<Integer> temp = new ArrayList<>();
//                for (int j = 0; j < additionalRocks + 1; j++) {
//                    temp.add(0);
//                }
//                dpList.add(temp);
//            }
//            for (int i = 1; i < dpList.size(); i++) {
//                for (int j = 1; j < additionalRocks + 1; j++) {
//                    int temp = Math.max(j - list.get(i - 1), -1);
//                    if (temp != -1) {
//                        dpList.get(i).set(j, (Math.max(dpList.get(i - 1).get(temp) + 1, dpList.get(i - 1).get(j - 1))));
//                    } else {
//                        dpList.get(i).set(j, dpList.get(i - 1).get(j - 1));
//                    }
//                }
//            }
//            return dpList.get(list.size()).get(additionalRocks) + max;
//        }
        return max;
    }

    public static void main(String[] args) {
        Solution2279 solution2279 = new Solution2279();
        System.err.println(solution2279.maximumBags(new int[] { 91,54,63,99,24,45,78 }, new int[] {35,32,45,98,6,1,25} , 17));
        System.err.println(solution2279.maximumBags(new int[] { 2,3,4,5 }, new int[] {1,2,4,4} , 2));
    }
}
